/*
  * @file DacAlgorithm.cpp
  * @author Thibault Merle et Guillaume Poussel
  */
#include <algorithm>

#include "base/Point.h"
#include "base/Vector.h"
#include "base/geometry.h"
#include "base/sorter.h"
#include "algo/DacAlgorithm.h"


/**
  * @brief Fusionne deux parties de l'enveloppe pour n'en faire qu'une.
  * @pre \p left et \p right sont deux enveloppes convexes
  * @param left Enveloppe de gauche
  * @param right Enveloppe de droite
  * @return Enveloppe globale
  */
point_list DaCAlgorithm::merge(point_list left,
                               point_list right) {
    // Premièrement, on récupère le point le plus à gauche de la partie droite
    // et le plus à droite de la partie gauche. Il s'agit des deux points
    // les plus proches de la ligne séparant les deux enveloppes.
    Point* it_ref_left = *max_element(left.begin(), left.end(), Lexicographic_Order());
    Point* it_ref_right = *min_element(right.begin(), right.end(), Lexicographic_Order());

    // Ensuite, on recherche le barycentre de chaque enveloppe
    Point* p_orig_left = left.get_centroid();
    Point* p_orig_right = right.get_centroid();

    // On range ensuite les points de chaque enveloppe respectivement
    // dans le sens horaire et anti-horaire
    left.sort(Clockwise_Order(p_orig_left, it_ref_left, true));
    delete p_orig_left;
    right.sort(Clockwise_Order(p_orig_right, it_ref_right, false));
    delete p_orig_right;

    point_list::iterator it_curr_left = left.begin();   // Point en cours sur l'enveloppe de gauche
    point_list::iterator it_curr_right = right.begin(); // et sur celle de droite
    point_list::iterator it_next_left = left.next_point(it_curr_left);    // Prochain point sur l'enveloppe de gauche
    point_list::iterator it_next_right = right.next_point(it_curr_right); // et sur celle de droite

    Vector bridgeLR(*it_curr_left, *it_curr_right); // Segment reliant l'enveloppe gauche à l'enveloppe droite
    Vector bridgeRL(*it_curr_right, *it_curr_left); // Segment opposé
    Vector curr_next_left(*it_curr_left, *it_next_left); // Segment en cours sur l'enveloppe de droite
    Vector curr_next_right(*it_curr_right, *it_next_right); // et sur celle de gauche

    // Recherche de la tangente inférieure
    bool finish;
    do {
        finish = true;
        // Parcours à gauche
        while (cross_product(&bridgeLR, &curr_next_left) < 0) {
            finish = false;
            left.advance(it_curr_left);
            left.advance(it_next_left);
            bridgeLR = Vector(*it_curr_left, *it_curr_right);
            bridgeRL = Vector(*it_curr_right, *it_curr_left);
            curr_next_left = Vector(*it_curr_left, *it_next_left);
        }
        // Parcours à droite
        while (cross_product(&curr_next_right, &bridgeRL) < 0) {
            finish = false;
            right.advance(it_curr_right);
            right.advance(it_next_right);
            bridgeLR = Vector(*it_curr_left, *it_curr_right);
            bridgeRL = Vector(*it_curr_right, *it_curr_left);
            curr_next_right = Vector(*it_curr_right, *it_next_right);
        }
    } while (!finish);

    // Suppression des points devenus inutiles
    left.erase(left.begin(), it_curr_left);
    right.erase(right.begin(), it_curr_right);

    // On remet les points de référence pour pouvoir chercher l'autre tangente
    left.push_back(it_ref_left);
    right.push_back(it_ref_right);

    // On retourne les deux enveloppes
    reverse(left.begin(), left.end());
    reverse(right.begin(), right.end());

    it_curr_left = left.begin();
    it_curr_right = right.begin();

    it_next_left = left.next_point(it_curr_left);
    it_next_right = right.next_point(it_curr_right);


    bridgeLR = Vector(*it_curr_left, *it_curr_right);
    bridgeRL = Vector(*it_curr_right, *it_curr_left);
    curr_next_left = Vector(*it_curr_left, *it_next_left);
    curr_next_right = Vector(*it_curr_right, *it_next_right);
    // Recherche de la tangente supérieure
    do {
        finish = true;
        // Parcours à gauche
        while (cross_product(&bridgeLR, &curr_next_left) > 0) {
            finish = false;
            left.advance(it_curr_left);
            left.advance(it_next_left);
            bridgeLR = Vector(*it_curr_left, *it_curr_right);
            bridgeRL = Vector(*it_curr_right, *it_curr_left);
            curr_next_left = Vector(*it_curr_left, *it_next_left);
        }
        // Parcours à droite
        while (cross_product(&curr_next_right, &bridgeRL) > 0) {
            finish = false;
            right.advance(it_curr_right);
            right.advance(it_next_right);
            bridgeLR = Vector(*it_curr_left, *it_curr_right);
            bridgeRL = Vector(*it_curr_right, *it_curr_left);
            curr_next_right = Vector(*it_curr_right, *it_next_right);
        }
    } while (!finish);
    // Seconde suppression des points devenus inutiles
    left.erase(left.begin(), it_curr_left);
    right.erase(right.begin(), it_curr_right);

    // On reconstitue l'enveloppe finale
    point_list result;
    result.insert(result.end(), left.begin(), left.end());
    result.insert(result.end(), right.rbegin(), right.rend());
    return result;
}

/**
  * @brief Calul de l'enveloppe convexe.
  *
  * @par "Complexité" Cette version est de complexité \f$O(n \log(n))\f$ puisqu'elle utilise une
  * méthode de type \e "Diviser pour régner".
  * @par "Algorithme" On appelle récursivement cette méthode sur les parties
  * gauche et droite de l'ensemble de points. Ensuite, on fusionne les deux
  * parties avec la méthode #merge.
  * @param points Liste des points en entrée
  * @return Liste des points constituant l'enveloppe convexe
  */
point_list DaCAlgorithm::compute(point_list points) {
    unsigned size = points.size();
    if (size <= 2) {
        // Avec deux points ou moins, l'enveloppe est constituée
        // de tous les points
        return points;
    }
    if (size == 3) {
        // Si il y a trois points, il faut vérifier s'ils ne sont pas alignés
        if (are_on_row(points[0], points[1], points[2])) {
            // Si oui, il faut retirer le point du milieu
            point_list hull;
            hull.push_back(*min_element(points.begin(), points.end(), Lexicographic_Order()));
            hull.push_back(*max_element(points.begin(), points.end(), Lexicographic_Order()));
            return hull;
        } else {
            return points;
        }
    }
    // Gestion d'un cas particulier un peu spécial (tous les points sont alignés verticalement)
    Point* min_x = *min_element(points.begin(), points.end(), Point_X_Order());
    Point* max_x = *max_element(points.begin(), points.end(), Point_X_Order());
    Point* min_y = *min_element(points.begin(), points.end(), Point_Y_Order());
    Point* max_y = *max_element(points.begin(), points.end(), Point_Y_Order());
    if (min_x->x() == max_x->x()) {
        point_list hull;
        hull.push_back(min_y);
        hull.push_back(max_y);
        return hull;
    } else if (min_y->y() == max_y->y()) {
        point_list hull;
        hull.push_back(min_x);
        hull.push_back(max_x);
        return hull;
    }

    // La taille est supérieure à 3, on utilise la récursivité
    // On supprime les doublons
    points.erase(unique(points.begin(), points.end(), Point_Comparator()), points.end());
    // Tri des points dans l'ordre lexicographique
    points.sort(Lexicographic_Order());

    // On coupe la liste en deux parties :
    // en cas de nombre impair, c'est la partie gauche qui sera plus petite
    point_list::iterator middle_it = points.begin();
    for (unsigned i = 0; i < size / 2; ++i) {
        ++middle_it;
    }
    point_list left(points.begin(), middle_it);
    point_list right(middle_it, points.end());

    // Appels récursifs
    point_list left_hull = compute(left);
    point_list right_hull = compute(right);

    // Fusion des deux enveloppes
    return merge(left_hull, right_hull);
}
